package com.leetcode.algorithm.y22.m07.w5;

import com.leetcode.algorithm.common.ListNode;

/**
 * 92. 反转链表 II
 * 
 * https://leetcode.cn/problems/reverse-linked-list-ii/
 * 
 * @author jie.deng
 *
 */
class Question0092Solution01 {

	public ListNode reverseBetween(ListNode head, int left, int right) {
		ListNode sentinel = new ListNode();
		sentinel.next = head;
		// 找到第left-1个节点
		ListNode prev = null;
		int cnt = left - 1;
		ListNode cur = sentinel;
		while (cnt > 0) {
			cur = cur.next;
			cnt--;
		}
		prev = cur;
		ListNode leftNode = prev.next;
		prev.next = null;

		// 找到第right+1个节点
		ListNode next = cur.next;
		cur = leftNode;
		cnt = right - left;
		while (cnt > 0) {
			cur = cur.next;
			cnt--;
		}
		ListNode rightNode = cur;
		next = cur.next;
		cur.next = null;

		// 翻转[left,right]
		reverse(leftNode);

		prev.next = rightNode;
		leftNode.next = next;

		return sentinel.next;
	}

	private void reverse(ListNode root) {
		if (root == null || root.next == null) {
			return;
		}
		reverse(root.next);
		root.next.next = root;
		root.next = null;
	}

}